// 题目要求：求字符串的全排列
// "ab" —> ["ab","ba"]
// "aab" -> ["aab","aba","baa"]

// 解题思路：
// 难点是剪枝：
// 1. 如果字符已经使用过了，那就不能再使用这个字符了 check[i] == false
// 2. 如果有重复字符：需要将字符全部排序
//    如果是排第一个字符，可以排 i == 0
//    如果是后面的字符，但是和它前面的字符是不相同的，那就也可以排 i > 0 && s[i] != s[i - 1]
//    如果是后面的字符，但是和它前面的字符是相同的，如果前面的字符用过了，就也可以排 i > 0 && s[i] == s[i - 1] && check[i] == true

import java.util.*;

public class Permutation {
    ArrayList<String> ret;
    StringBuilder path;
    boolean[] check;
    char[] s;
    int n = 0;
    public ArrayList<String> PermutationFunc (String str) {
        s = str.toCharArray();
        n = s.length;

        ret = new ArrayList<>();
        path = new StringBuilder();
        check = new boolean[n];

        Arrays.sort(s);

        dfs();

        return ret;
    }

    public void dfs(){
        if(path.length() >= n) {
            ret.add(path.toString());
            return;
        }
        for(int i = 0; i < n; i++){
            if(check[i] != true && (i == 0 || (i > 0 && (s[i] != s[i - 1] || check[i - 1])))){
                path.append(s[i]);
                check[i] = true;
                dfs();
                check[i] = false;
                path.deleteCharAt(path.length() - 1);
            }
        }
    }
}
